package com.lw.leetcode.binary.c;

/**
 * Created with IntelliJ IDEA.
 * 1095. 山脉数组中查找目标值
 *
 * @author liw
 * @version 1.0
 * @date 2022/5/17 15:45
 */
public class FindInMountainArray {

    public int findInMountainArray(int target, MountainArray mountainArr) {
        int length = mountainArr.length();
        int mid = find(mountainArr);
        int finda = finda(target, mountainArr, 0, mid);
        if (finda != -1) {
            return finda;
        }
        return findb(target, mountainArr, mid + 1, length - 1);
    }

    private int finda(int target, MountainArray mountainArr, int st, int end) {
        while (st <= end) {
            int m = st + ((end - st) >> 1);
            if (mountainArr.get(m) == target) {
                return m;
            } else if (mountainArr.get(m) < target) {
                st = m + 1;
            } else {
                end = m - 1;
            }
        }
        return -1;
    }

    private int findb(int target, MountainArray mountainArr, int st, int end) {
        while (st <= end) {
            int m = st + ((end - st) >> 1);
            if (mountainArr.get(m) == target) {
                return m;
            } else if (mountainArr.get(m) < target) {
                end = m - 1;
            } else {
                st = m + 1;
            }
        }
        return -1;
    }

    private int find(MountainArray mountainArr) {
        int st = 0;
        int end = mountainArr.length() - 1;
        while (st < end) {
            if (end - st < 3) {
                return st + 1;
            }
            int m = st + ((end - st) >> 1);
            if (mountainArr.get(m) > mountainArr.get(m - 1) && mountainArr.get(m) > mountainArr.get(m + 1)) {
                return m;
            } else if (mountainArr.get(m) > mountainArr.get(m - 1)) {
                st = m;
            } else {
                end = m;
            }
        }
        return -1;
    }

    interface MountainArray {
        int get(int index);

        int length();
    }
}
